This invention is directed to a method of offline personal authentication involving a secret user personal identification number (PIN), a secret key and other nonsecret data stored on a customer memory card, and a nonsecret validation value stored in each terminal connected in a network. Typically, the terminals are connected to a bank which issues the memory card and the terminals are automated teller machines (ATM) or point of sale (POS) terminals. By memory card, what is meant is a card which stores more binary data than currently used magnetic stripe cards but is distinguished from so-called "smart" cards in that it does not incorporate a microprocessor on the card.
The problem solved by the subject invention is that of authenticating a user of a memory card for electronic funds transfer (EFT) systems or point of sale (POS) terminals. The subject invention is based on a technique of "tree authentication" first suggested by Ralph Merkle. See, for example, the following publications:
Ralph C. Merkle, Secrecy, Authentication, and Public Key Systems, UMI Research Press, Ann Arbor, Mich., 1982.
Ralph C. Merkle, Secrecy, Authenication, and Public Key Systems, Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, June 1979.
Ralph C. Merkle, Protocols for Public Key Cryptosystems, Technical Report, BNR, Palo Alto, CA, January 1980.
Ralph C. Merkle, "Protocols for Public Key Cryptosystems," Proceedings of the 1980 Symposium on Security and Privacy, 122-134, Apr. 14-16, 1980).
U.S. Pat. No. 4,309,569 to Ralph C. Merkle for "Method of Providing Digital Signatures" discloses a method of providing a digital signature for purposes of authentication of a message. This method utilizes an authentication tree function or a one-way function of a secret number. More specifically, the method according to Merkle provides a digital signature of the type which generates a secret number X.sub.i, where X.sub.i =x.sub.i1, x.sub.i2, x.sub.i3, . . . , x.sub.in, computes Y.sub.i =F(X.sub.i) and transmits part of X.sub.i to the receiver as the digital signature. Merkle characterizes his invention as providing an authentication tree with an authentication tree function comprising a one-way function of Y.sub.i. The root of the authentication tree and the authentication free function are authenticated at the receiver. The Y.sub.i and the corresponding authentication path values of the authentication tree are transmitted from the transmitter to the receiver. Finally, the Y.sub.i are authenticated at the receiver by computing the authentication path of the authentication tree between the Y.sub.i and the rest of the authentication tree.
The Merkle method is specifically intended to be an improvement over a public key cryptosystem proposed by Diffie et al. in "New Directions in Cryptography," IEEE Transactions on Information Theory, vol. IT-22, no. 6, November 1976, pages 644 to 654, as a means to implement a digital signature and authenticate the true content of a message. In the Diffie et al. scheme, to sign a message m whose size is s bits, it is necessary to compute F(x.sub.1)=y.sub.1, F(x.sub.2)=y.sub.2, . . . , F(x.sub.s)=y.sub.s. The transmitter and receiver would agree on the vector Y=y.sub.1, y.sub.2, . . . , y.sub.s. If the jth bit of m was a 1, the transmitter would reveal x.sub.j ; but if the jth bit of m was a 0, the transmitter would not reveal x.sub.j. In essence, each bit of m would be individually signed. To avoid the possibility of altering m by the receiver, Diffie et al. signed a new message m' that was twice as long as m and computed by concactenating m with the bitwise complement of m. This meant that each bit m.sub.j in the original message was represented by two bits, one of which would not be altered by the receiver.
A major problem of the Diffie et al. method addressed by Merkle was that it was only practical between a single pair of users. Accordingly, Merkle's approach provided a signature system of more general application and which rested on the security of a conventional cryptographic function. Moreover, Merkle's authentication tree required less storage than the Diffie et al. method. Merkle showed that n values of m bits each could be authenicated on the basis of only m.times.log.sub.2 (n) bits of nonsecret information, where ".times." denotes multiplication. The one-way function that Merkle envisioned called for a value of m=100, although that is not significant in terms of the raw algorithm. The present invention adapts Merkle's idea of tree authentication to the area of offline EFT/POS banking.